package Leetcode.排序;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @ClassName 最大子序列的分数
 * @since: 2023/9/9 10:09
 * @auth: kirito
 * @description:
 * 给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都是 n ，再给你一个正整数 k 。你必须从 nums1 中选一个长度为 k 的 子序列 对应的下标。
 *
 * 对于选择的下标 i0 ，i1 ，...， ik - 1 ，你的 分数 定义如下：
 *
 * nums1 中下标对应元素求和，乘以 nums2 中下标对应元素的 最小值 。
 * 用公式表示： (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]) 。
 * 请你返回 最大 可能的分数。
 *
 * 一个数组的 子序列 下标是集合 {0, 1, ..., n-1} 中删除若干元素得到的剩余集合，也可以不删除任何元素。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
 * 输出：12
 * 解释：
 * 四个可能的子序列分数为：
 * - 选择下标 0 ，1 和 2 ，得到分数 (1+3+3) * min(2,1,3) = 7 。
 * - 选择下标 0 ，1 和 3 ，得到分数 (1+3+2) * min(2,1,4) = 6 。
 * - 选择下标 0 ，2 和 3 ，得到分数 (1+3+2) * min(2,3,4) = 12 。
 * - 选择下标 1 ，2 和 3 ，得到分数 (3+3+2) * min(1,3,4) = 8 。
 * 所以最大分数为 12 。
 * 示例 2：
 *
 * 输入：nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
 * 输出：30
 * 解释：
 * 选择下标 2 最优：nums1[2] * nums2[2] = 3 * 10 = 30 是最大可能分数。
 **/
public class 最大子序列的分数 {
    /**
     要用long,否则溢出提交报错
     本解法其实也是暴力算法,遍历所有情况,只不过是采用了排序和最小堆的方式确立一个遍历的方式
     从审题我们知道这都是正整数,如果不是的话,排序毫无意义了,因为负负得正,有可能更高,既然都是正整数,
     那么乘法的权重肯定是要比加法的权重要高得多的,所以我们先给nums2来降序, 降序之后,
     此时,k就能翻译成nums2的前k个
     */
    /**
     假设 nums1[1,3,3,2] nums2[2,1,3,4],k为3
     */
    public long maxScore(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;

        Integer [] idxs = new Integer[n];
        for (int i = 0; i < n; i ++){
            idxs[i] = i;
        }
        //  (i, j) -> nums2[j] - nums2[i] 是一个比较器，用于确定排序的规则。在比较器中，(i, j) 表示两个元素的索引。
        //nums2[j] - nums2[i] 表示以 nums2 数组中的元素作为排序的依据，按照降序进行排序。如果 nums2[j] - nums2[i] 的值为正数，
        //则 j 的位置在前，i 的位置在后；如果为负数，则 i 的位置在前，j 的位置在后；如果为零，则两个元素相等，位置不变。
        // 这样的排序规则可以实现按照 nums2 中的元素从大到小对 idxs 数组进行排序，使得 idxs 中的元素按照对应的 nums2 中的元素值降序排列
        // 比如,在nums2里的是[2,1,3,4](对应的下标是[0,1,2,3]),如果对nums2排序的话[4,3,2,1](对应的下标是[3,2,0,1]), 此时 idxs为[3,2,0,1]
        Arrays.sort(idxs, (i, j) -> nums2[j] - nums2[i]);

        long res = 0L;
        // 最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        long sum1 = 0;
        for (int idx: idxs){
            // nums1是被动的跟随nums2取值的
            int x = nums1[idx];
            int y = nums2[idx];


            while (minHeap.size() > k - 1){
                // 这个是k个元素都够了以后,还要继续遍历的时候才会进入,比如前k是4 3 2的时候,最小的是2,那么向下移动一个位置,
                // 变成3 2 1的时候,该把nums1里的谁踢掉呢,
                // 此时,因为nums2有了1的加入,1是最小的了,在k里的num2的其他元素在min()函数里没有意义了,
                // 此时看公式的另一项了,num1还是有作用的,因此去掉num1构件的最小堆里最小的值,也就是1
                // nums2  nums1          nums2   nums1
                // * * *                 * * *
                // * 4 *     2           * 4 *      2
                // * 3 *     3           * 3 *      3
                // * 2 *     1   >>>     * * *
                // * * *                   2        1 //这个从最小堆中踢掉
                //   1       3           * * *
                //                       * 1 *      3
                //                       * * *
                sum1 -= minHeap.poll();
            }
            minHeap.offer(x);
            sum1 += x;
            // 当符合这个条件时,y刚好就是前k个元素里最小的
            if (minHeap.size() == k){
                long cur = sum1 * y;
                res = Math.max(res, cur);
            }
        }

        return res;
    }


}
